package main

import "strings"

func main() {
	// [28. 找出字符串中第一个匹配项的下标](https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/)
	// [459. 重复的子字符串](https://leetcode.cn/problems/repeated-substring-pattern/)
	// [232. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/)
	// [225. 用队列实现栈](https://leetcode.cn/problems/implement-stack-using-queues/)
	// [20. 有效的括号](https://leetcode.cn/problems/valid-parentheses/)
}

// 28
func strStr(haystack string, needle string) int {
	next := make([]int, len(needle))
	getNext(next, needle)
	j := 0
	for i := 0; i < len(haystack); i++ {
		// 不相等，回退
		for j > 0 && haystack[i] != needle[j] {
			j = next[j-1]
		}
		// 相等，增加
		if haystack[i] == needle[j] {
			j++
		}
		// j到了末尾，说明匹配完了
		if j == len(next) {
			return i - len(needle) + 1
		}
	}
	return -1
}

func getNext(next []int, s string) {
	// 初始化前缀表
	j := 0
	next[0] = 0
	for i := 1; i < len(s); i++ {
		// 不相等，退回
		if j > 0 && s[i] != s[j] {
			j = next[j-1]
		}
		// 相等，增加
		if s[i] == s[j] {
			j++
		}
		next[i] = j
	}
}

// 459
func repeatedSubstringPattern(s string) bool {
	// abab+abab = bababa
	// aba+aba = baab
	str := []byte(s)
	ss := string(str[1:]) + string(str[:len(str)-1])
	return strings.Contains(ss, s)
}

// 232
type MyQueue struct {
	st1 []int
	st2 []int
}

func Constructor() MyQueue {
	return MyQueue{
		st1: make([]int, 0),
		st2: make([]int, 0),
	}
}

func (this *MyQueue) Push(x int) {
	this.st1 = append(this.st1, x)
}

func (this *MyQueue) Pop() int {
	if len(this.st2) != 0 {
		x := this.st2[0]
		this.st2 = this.st2[1:]
		return x
	} else {
		this.st2 = this.st1
		this.st1 = make([]int, 0)
		return this.Pop()
	}
}

func (this *MyQueue) Peek() int {
	if len(this.st2) != 0 {
		x := this.st2[0]
		return x
	} else {
		this.st2 = this.st1
		this.st1 = make([]int, 0)
		return this.Peek()
	}
}

func (this *MyQueue) Empty() bool {
	return len(this.st1) == 0 && len(this.st2) == 0
}

// 225
type MyStack struct {
	queue []int
}

func Constructor() MyStack {
	return MyStack{
		queue: make([]int, 0),
	}
}

func (this *MyStack) Push(x int) {
	this.queue = append(this.queue, x)
}

func (this *MyStack) Pop() int {
	size := len(this.queue)
	size--
	for size > 0 {
		val := this.queue[0]
		this.queue = this.queue[1:]
		this.Push(val)
		size--
	}
	val := this.queue[0]
	this.queue = this.queue[1:]
	return val
}

func (this *MyStack) Top() int {
	x := this.queue[len(this.queue)-1]
	return x
}

func (this *MyStack) Empty() bool {
	return len(this.queue) == 0
}

// 20
func isValid(s string) bool {
	n := len(s)
	if n%2 == 1 {
		return false
	}
	mp := map[byte]byte{')': '(', ']': '[', '}': '{'}
	stack := make([]byte, 0)
	for i := 0; i < n; i++ {
		if mp[s[i]] > 0 {
			if len(stack) == 0 || stack[len(stack)-1] != mp[s[i]] {
				return false
			}
			stack = stack[:len(stack)-1]
		} else {
			stack = append(stack, s[i])
		}
	}
	return len(stack) == 0
}
